Logic Workshop

The lattice problem for models of PA is to determine which lattices can be represented either as lattices of elementary substructures of a model of PA or, more generally, which can be represented as lattices of elementary substructures of a model N that contain a given elementary substructure M of N.

Since the 1970's, the problem generated much research with highly nontrivial results with proofs combining specific methods in the model theory of arithmetic with lattice theory and various combinatorial theorems. The problem has a definite answer in the case of distributive lattices, and, despite much effort, there are still many open questions in the nondistributive case. I will briefly survey some early results and present a few proofs that illustrate the difference between the distributive and nondistributive cases.

In this talk we discuss the computability of the entropy $H_{\rm top}(X)$ and topological pressure $P_{\rm top}(\phi)$ on compact shift spaces $X$ and continuous potentials $\phi:X\to\mathbb R$. This question has recently been studied for subshifts of finite type (SFTs) and their factors (Sofic shifts). We develop a framework to address the computability of the entropy pressure on general shift spaces and apply this framework to coded shifts. In particular, we prove the computability of the topological pressure for all continuous potentials on S-gap shifts, generalized gap shifts, and Beta shifts. We also construct shift spaces which, depending on the potential, exhibit computability and non-computability of the topological pressure. We further show that the generalized pressure function $(X,\phi)\mapsto P_{\rm top}(X,\phi\vert_{X})$ is not computable for a large set of shift spaces $X$ and potentials $\phi$. Along the way of developing these computability results, we derive several ergodic-theoretical properties of coded shifts which are of independent interest beyond the realm of computability. The topic of the talk is joint work with Michael Burr (Clemson U.), Shuddho Das (Texas Tech) and Yun Yang (Virginia Tech).

When does a hyperarchimedean lattice-ordered group embed into a hyperarchimedean lattice-ordered group with strong unit? After explaining the meaning of this question, I will describe some partial answers obtained via model theory.

I will give a brief survey how tools from algebraic geometry can be used in finding solutions to Diophantine equations over $F_p[[t]]$ and similar rings. These tools include Artin approximation, arc spaces, motives and resolution of singularities. This approach yields the definability of the existential theory of $F_p[[t]]$ (in the ring language with a constant for $t$) contingent upon the validity of resolution of singularities (Denef-Schoutens). Anscombe-Fehm proved a weaker result using model-theoretic tools and together with Dittmann, they gave a proof assuming only the weaker 'local uniformization conjecture.'

In 1911, Dehn proposed three decision problems for finitely presented groups: the word problem, the conjugacy problem, and the isomorphism problem. These problems have been central to both group theory and logic, and were each proven to be undecidable in the 50's. There is much current research studying the decidability of these problems in certain classes of groups.

Classically, when a decision problem is undecidable, its complexity is measured using Turing reducibility. However, Dehn's problems can also be naturally thought of as computably enumerable equivalence relations (ceers). We take this point of view and measure their complexity using computable reductions. This yields behaviors different from the classical context: for instance, every Turing degree contains a word problem, but not every ceer degree does. This leads us to study the structure of ceer degrees containing a word problem and other related questions.

In the late 1910s Bertrand Russell was occupied with two things: getting into political trouble for his pacifism and trying to understand the foundations of mathematics. His students were hard at work with him on this second occupation. One of those students was Dorothy Wrinch. In 1923 she gave a characterization of the axiom of choice in terms of a generalization of the notion of a Dedekind-finite infinite set. Unfortunately, her career turned toward mathematical biology and her logical work was forgotten by history.

This talk is part of a project of revisiting Wrinch's work from a modern perspective. I will present the main result of her 1923 paper, that AC is equivalent to the non-existence of what she termed mediate cardinals. I will also talk about some new independence results. The two main results are: (1) the smallest $\kappa$ for which a $\kappa$-mediate cardinal exists can consistently be any regular $\kappa$ and (2) the collection of regular $\kappa$ for which exact $\kappa$-mediate cardinals exist can consistently be any class.

A computable quotient presentation of a mathematical structure $\mathcal A$ consists of a computable structure on the natural numbers $\langle \mathbb{N},\star,\ast,\dots \rangle$, meaning that the operations and relations of the structure are computable, and an equivalence relation $E$ on $\mathbb{N}$, not necessarily computable but which is a congruence with respect to this structure, such that the quotient $\langle \mathbb{N},\star,\ast,\dots \rangle$ is isomorphic to the given structure $\mathcal{A}$. Thus, one may consider computable quotient presentations of graphs, groups, orders, rings and so on.
A natural question asked by B. Khoussainov in 2016, is if the Tennenbaum Thoerem extends to the context of computable presentations of nonstandard models of arithmetic. In a joint work with J.D. Hamkins we have proved that no nonstandard model of arithmetic admits a computable quotient presentation by a computably enumerable equivalence relation on the natural numbers.
However, as it happens, there exists a nonstandard model of arithmetic admitting a computable quotient presentation by a co-c.e. equivalence relation. Actually, there are infinitely many of those. The idea of the proof consists is simulating the Henkin construction via finite injury priority argument. What is quite surprising, the construction works (i.e. injury lemma holds) by Hilbert's Basis Theorem. The latter argument is joint work with T. Slaman and L. Harrington.

A structure, R, expanding $(\mathbb{R}, \lt)$ is called component closed if whenever $X \subseteq R^n$ is definable so are all of $X$'s connected components. Two basic examples of component closed structures are $(\mathbb{R}, \lt, +, \cdot)$ and $(\mathbb{R}, \lt, \cdot, \mathbb{Z})$. It turns out that these two structures are exemplary of a general phenomenon for component closed structures from a broad class of expansions of $(\mathbb{R}, \lt)$: either their definable sets are very 'tame' (as in the case of the real closed field) or they are quite 'wild' (as in the case of the real field expanded by the integers).

The Tukey order finds its origins in the concept of Moore-Smith convergence in topology, and is especially important when restricted to ultrafilters with reverse inclusion. The Tukey order of ultrafilters over $\omega$ was studied intensively by Blass, Dobrinen, Isbell, Raghavan, Shelah, Todorcevic and many others, but still contains many fundamental unresolved problems. After reviewing the topological background for the Tukey order, I will present a recent development in the theory of the Tukey order restricted to ultrafilters on measurable cardinals, and explain how different the situation is when compared to ultrafilters on $\omega$. Moreover, we will see an important application to the Galvin property of ultrafilters. In the second part of the talk, we will demonstrate how ideas and intuition from ultrafilters over measurable cardinals lead to new results on the Tukey order restricted to ultrafilters over $\omega$. This is joint with Natasha Dobrinen.

In their 1979 paper `Minimal Infinite Topological Spaces,’ Ginsburg and Sands proved that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on $\omega$: indiscrete, discrete, initial segment, final segment, and cofinite. The proof, while nonconstructive, features an interesting application of Ramsey's theorem for pairs ($\mathsf{RT}^2_2$). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg-Sands theorem for CSC spaces is equivalent to $\mathsf{ACA}_0,$ while for Hausdorff spaces it is provable in $\mathsf{RCA}_0$. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg-Sands theorem turns out to be equivalent to the Chain-Antichain Principle ($\mathsf{CAC}$). The most surprising case is that of the Ginsburg-Sands theorem restricted to $T_1$ spaces. Here, we show that the principle lies strictly between $\mathsf{ACA}_0$ and $\mathsf{RT}^2_2$, yielding perhaps the first natural theorem of ordinary mathematics (i.e., conceived outside of logic) to occupy this interval. I will discuss the proofs of both the implications and separations, which feature several novel combinatorial elements, and survey a new class of purely combinatorial principles below $\mathsf{ACA}_0$ and not implied by $\mathsf{RT}^2_2$ revealed by our investigation. This is joint work with Heidi Benham, Andrew DeLapo, Reed Solomon, and Java Darleen Villano.

The algebraic field extensions of the rational numbers $\mathbb{Q}$ – equivalently, the subfields of the algebraic closure $\overline{\mathbb{Q}}$ – naturally form a topological space homeomorphic to Cantor space. Consequently, one can speak of 'large' collections of such fields, in the sense of Baire category: collections that are comeager in the space. Under a standard definition, the 1-generic fields form a comeager set in this space. Therefore, one may think of a property common to all 1-generic fields as a property that one might reasonably expect to be true of an arbitrarily chosen algebraic field.

We will present joint work with Eisenträger, Springer, and Westrick that proves several intriguing properties to be true of all 1-generic fields $F$. First, in every such $F$, both the subring $\mathbb{Z}$ of the integers and the subring $\mathcal{O}_F$ of the algebraic integers of $F$ cannot be defined within $F$ by an existential formula, nor by a universal formula. (Subsequent work by Dittman and Fehm has shown that in fact these subrings are completely undefinable in these fields.) Next, for every presentation of every such $F$, the root set

$ R_F = \{ p\in \mathbb{Z}[X]:p(X)=0\text{ has a solution in }F\} $

is always of low Turing degree relative to that presentation, but is essentially always undecidable relative to the presentation. Moreover, the set known as Hilbert's Tenth Problem for $F$,

$ HTP(F) = \{ p\in \mathbb{Z}[X_1,X_2,\ldots]:p(X_1,\ldots,X_n)=0\text{ has a solution in }F^n\}, $

is exactly as difficult as $R_F$, which is its restriction to single-variable polynomials. Finally, even the question of having infinitely many solutions,

$\{ p\in \mathbb{Z}[X_1,X_2,\ldots]:p(\vec{X})=0\text{ has infinitely many solutions in }F^n\}, $

is only as difficult as $R_F$. These results are proven by using a forcing notion on the fields and showing that it is decidable whether or not a given condition forces a given polynomial to have a root, or to have infinitely many roots.

For a cardinal $\kappa\ge 2$, one can weaken the concept 'x is ordinal definable' (i.e., x is the unique object satisfying some condition involving ordinal parameters) to 'x is $\lt\kappa$-blurrily ordinal definable,' meaning that x is one of fewer than $\kappa$ many objects satisfying some condition involving ordinal parameters. By considering the hereditary version of this, one naturally arrives at the inner model $\lt\kappa$-HOD, the class of all hereditarily $\lt\kappa$-blurrily ordinal definable sets. In ZFC, by varying $\kappa$, one obtains a hierarchy of inner models spanning all the way from HOD to V. The leaps are those stages in the hierarchy where something new is added. I have previously given a logic workshop talk about the basic theory of the blurry HOD hierarchy, and in this talk, after reviewing the basics, I want to focus on the consistency strengths of certain leap constellations, ranging from outright consistent, to equiconsistent with a measurable cardinal, to inconsistent.